МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Структура даних ЧЕРГА Звіт до лабораторної роботи № 4 з дисципліни " Програмування. Частина III. Структури даних та алгоритми " № варіанту=[(8+75+114)]%30+1=18 1)Мета роботи:вивчити фундаментальну абстрактну структуру даних - чергу. Набути практичних навичок побудови черги, дослідити динаміку її вмісту та використання черги для розв'язання прикладних задач. 2)Постановка завдання: Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queue underflow) і "переповнення черги" (queue overflow) або "втрати значимості деку"(deq underflow) і "переповнення деку" (deq overflow). Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами. Змоделювати чергу за допомогою двух стеків. Додавання елементу до черги зводиться до додавання до одному зі стеков, а перевірка, чи черга порожня - до перевірки, чи порожні обидва стеки. При вилученні елемента з черги можливі два випадки. Якщо стек, де знаходиться початок черги, не порожній, то вилучається з нього елемент. Якщо він порожній, то попередньо в нього переписуються всі елементи другого стеку, змінюючи порядок (це відбувається автоматично при перекладанні елементів з одного стеку в інший) і далі задача зводиться до першого випадку. 3) Алгоритм розв’язання задачі: Моделюю чергу за допомогою двох стеків. Ми у стек S2 додаємо числа, коли ми вилучаємо число то у нас є два випадки вилучення: 1) Якщо стек, де знаходиться початок черги, не порожній, то вилучається з нього елемент. 2) Якщо він порожній, то попередньо в нього переписуються всі елементи другого стеку, змінюючи порядок (це відбувається автоматично при перекладанні елементів з одного стеку в інший) і далі задача зводиться до першого випадку. 4)Динаміка вмісту черги: S1 S2                   Data[0]                     Data[0]   Puch 4                   Data[0]                   4  Data[0]   Puch6                   Data[0]                   6  Data[1] Data[0]   4    Pop()                   Data[0]   6                      Data[0]    Push5                   Data[0]   6                    5  Data[0]   Pop()                   Data[0]   6                      Data[0]   Висновок: На даній лабораторній роботі я вивчив фундаментальну абстрактну структуру даних - чергу. Набув практичних навичок побудови черги, дослідив динаміку її вмісту та використання черги для розв'язання прикладних задач